/**
 * 给定数组A，操作K次，每次选A中最小最前的元素将其乘M
 * 最后输出数组A取模的结果
 * K在1E9因此不能直接模拟。
 * 观察一下可知，当轮到原数组的max开始做乘法操作时，到下次该max操作之前，是一轮操作
 * 且以后必然往复操作。
 * 因此首先求出前序操作的序列，然后再求出往复操作的序列，再结合K可以直到每个元素上面要乘多少个M
 * 然后快速幂取模即可。
 * 操作序列可以用优先队列求得
 * 元素值在1E9，前序操作的数量最多为(10000 * 20)
 * 往复操作的数量应该不多？，最多为（10000 * 20）
 * 求取操作序列的时间复杂度为O(20NlogN)
 * 后面的计算，不考虑快速幂的时间O(N)即可。
 */
class Solution {
    using llt = __int128_t;

public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        if(1 == multiplier) return nums;

        vector<llt> vec(nums.begin(), nums.end());
        vector<int> op;
        int mmin = 0, mmax = 0;
        int n = vec.size();
        for(int i=0;i<n;++i){
            if(vec[i] < vec[mmin]) mmin = i;
            if(vec[mmax] <= vec[i]) mmax = i;
        }

        priority_queue<int, vector<int>, function<bool(int, int)>> q([&](int a,int b)->bool{
            if(vec[a] != vec[b]) return vec[a] > vec[b];
            return a > b;
        });

        for(int i=0;i<n;++i) q.push(i);

        while(1){
            int h = q.top(); q.pop();
            if(h == mmax){               
                break;
            }
            
            op.emplace_back(h);
            vec[h] *= multiplier;
            q.push(h);
        }

        static llt const MOD = 1E9 + 7;

        if(k <= op.size()){
            for(int i=0;i<k;++i){
                nums[op[i]] = (llt)nums[op[i]] * multiplier % MOD;
            }
            return nums;
        }else{
            for(auto i : op){
                nums[i] = (llt)nums[i] * multiplier % MOD;
            }
        }

        vector<int> oop;
        while(not q.empty()) q.pop();
        oop.emplace_back(mmax);
        vec[mmax] *= multiplier;
        for(int i=0;i<n;++i) q.push(i);
        while(1){
            int h = q.top(); q.pop();
            if(h == mmax) break;

            oop.emplace_back(h);
            vec[h] *= multiplier;
            q.push(h);
        }

        k -= op.size();

        int round = k / oop.size();
        int left = k % oop.size();

        vector<int> cnt(nums.size(), 0);
        for(const auto & p : oop){
            cnt[p] += 1;
        }
        
        for(int i=0;i<n;++i){
            nums[i] = nums[i] * qpow(multiplier, round * cnt[i]) % MOD;
        }

        for(int i=0;i<left;++i){
            nums[oop[i]] = ((llt)nums[oop[i]]) * multiplier % MOD;
        }
        
        return nums;
    }

    static llt qpow(llt a, llt n){
        static const llt MOD = 1E9+7;
        a %= MOD;
        llt ret = 1;
        while(n){
            if(n & 1) ret = ret * a % MOD;
            a = a * a % MOD;
            n >>= 1;
        }
        return ret;
    }
};